// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 将两个字符串作为输入并返回它们最长公共子序列的长度。
func LCS(str1 string, str2 string) int {
	//求两个字符串的长度
	m, n := len(str1), len(str2)

	//为动态规划创建记忆矩阵
	memo := make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		memo[i] = make([]int, n+1)
		for j := 0; j < n+1; j++ {
			memo[i][j] = -1
		}
	}

	//使用记忆调用 lcs() 函数
	return lcs(str1, str2, m, n, &memo)
}

// 返回两个字符串之间最长公共子序列的长度
func lcs(s1, s2 string, m, n int, memo *[][]int) int {
	//如果任一字符串为空，则返回 0
	if m == 0 || n == 0 {
		return 0
	}

	//检查这个子问题的结果是否已经计算出来，如果是则返回
	if (*memo)[m][n] != -1 {
		return (*memo)[m][n]
	}

	//如果两个字符串的最后一个字符匹配，则将 LCS 加 1，并对剩余的字符串进行递归
	if s1[m-1] == s2[n-1] {
		(*memo)[m][n] = 1 + lcs(s1, s2, m-1, n-1, memo)
	} else {
		//如果最后一个字符不匹配，则通过排除 str1 或 str2 的最后一个字符并取两个值中的最大值来重复这两个字符串
		(*memo)[m][n] = max(lcs(s1, s2, m-1, n, memo), lcs(s1, s2, m, n-1, memo))
	}

	//返回此子问题的结果
	return (*memo)[m][n]
}

// 返回两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func main() {
	// 声明变量
	str1 := "lovego"
	str2 := "lvo"
	res := LCS(str1, str2)
	fmt.Println(res)
}

//$ go run interview12-2.go
//3
